public class AVLTree {
    static class TreeNode{
        int bf;
        int val;
        TreeNode parent;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    TreeNode root;

    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root==null){
            root=node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                return false;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }
        }
        if(parent.val>val){
            parent.left=node;
        }else{
            parent.right=node;
        }

        node.parent=parent;
        cur=node;
        while(parent!=null){
            if (cur==parent.left){
                parent.bf--;
            }else{
                parent.bf++;
            }
            if(parent.bf==-1||parent.bf==1){
                cur=parent;
                parent=parent.parent;
            }else{
                if(parent.bf==0) {
                    break;
                }
                else {
                    if(parent.bf==2){
                        if(cur.bf==1){
                            //左单旋
                            rotateLeft(parent);
                        }else{
                            //cur.bf==-1--->右左双旋
                            rotateRL(parent);
                        }
                    }else {
                        if (cur.bf==-1){
                            //右单旋
                            rotateRight(parent);
                        }
                        else{
                            //cur.bf==1 左右双旋
                            rotateLR(parent);
                        }
                    }
                    break;
                }
            }
        }
        return true;
    }
    private void rotateLeft(TreeNode parent){
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left;

        parent.right=subRL;
        subR.left=parent;
        if (subRL!=null){
            subRL.parent=parent;
        }
        TreeNode parentP=parent.parent;
        subR.parent=parentP;
        if(parent==root){
            root=subR;
            root.parent=null;
        }else if(parentP.left==parent){
            parentP.left=subR;
        } else {
            parentP.right=subR;
        }
        parent.parent=subR;
        parent.bf=0;
        subR.bf=0;
    }
    private void rotateRight(TreeNode parent){
        TreeNode subL=parent.left;
        TreeNode subLR=subL.right;

        parent.left=subLR;
        subL.right=parent;

        TreeNode parentP=parent.parent;
        if(subLR!=null){
            subLR.parent=parent;
        }
        if(parent==root){
            root=subL;
            subL.parent=null;
        }else{
            if (parentP.left==parent){
                parentP.left=subL;
            } else {
                parentP.right=subL;
            }
            subL.parent=parentP;
        }
        parent.parent=subL;
        parent.bf=0;
        subL.bf=0;
    }
    private void rotateRL(TreeNode parent){
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left;
        int bf=subRL.bf;

        rotateRight(subR);
        rotateLeft(parent);

        if(bf==1){
            parent.bf=-1;
            subR.bf=0;
            subRL.bf=0;
        }else{
            if (bf==-1){
                parent.bf=0;
                subR.bf=1;
                subRL.bf=0;
            }
        }
    }
    private void rotateLR(TreeNode parent){
        TreeNode subL=parent.left;
        TreeNode subLR=parent.right;
        int bf=subLR.bf;

        rotateLeft(subL);
        rotateRight(parent);

        if (bf==1){
            subLR.bf=0;
            subL.bf=-1;
            parent.bf=0;
        }else{
            if (bf==-1){
                subLR.bf=0;
                parent.bf=1;
                subL.bf=0;
            }
        }
    }
    //中序遍历
    public void inorder(TreeNode root){
        if (root==null) return ;
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }
    public int height(TreeNode root){
        if (root==null) return 0;
        int leftH=height(root.left);
        int rightH=height(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }

    //判断平衡树是否平衡
    public boolean isBalance(TreeNode root){
        if (root==null) return true;
        int leftH=height(root.left);//节点左边的高度
        int rightH=height(root.right);//节点右边的高度

        //判断平衡因子是否正确
        if(root.bf!=rightH-leftH){
            System.out.println("这个平衡因子异常："+ root.val+" "+root.bf);
            return false;
        }

        return Math.abs(leftH-rightH)<=1&&isBalance(root.left)&&isBalance(root.right);
    }
    //检验全部节点平衡信息是否正确
    public boolean detection(TreeNode root){
        if(root==null) return true;
        return isBalance(root)&&isBalance(root.left)&&isBalance(root.right);
    }
}
